package datastruct.tree;

public class Trie {

    TrieNode root;

    public Trie(){
        root = new TrieNode();
    }

    public void insert(String word){
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i)-'a';
            if(cur.trieNodes[idx]==null){
                cur.trieNodes[idx] = new TrieNode();
            }
            cur = cur.trieNodes[idx];
        }
        cur.isEnd = true;
    }

    public boolean search(String word){
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i)-'a';
            if(cur.trieNodes[idx]==null) return false;
            cur = cur.trieNodes[idx];
        }
        return cur.isEnd;
    }

    public boolean startsWith(String prefix){
        TrieNode cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            int idx = prefix.charAt(i)-'a';
            if(cur.trieNodes[idx]==null) return false;
            cur = cur.trieNodes[idx];
        }
        return true;
    }
}

class TrieNode{
    TrieNode[] trieNodes; //26个小写英文字母
    boolean isEnd; //是否代表一个单词的结束
    TrieNode(){
        trieNodes = new TrieNode[26];
        isEnd = false;
    }
}
